package com.zlsy.learning.leetcode.linkedlist.l21;

import com.zlsy.learning.leetcode.linkedlist.l234.ListNode;

/**
 * @author zhouliang
 * @date 2020/8/6 14:27 l1和l2合并，并组成一个新的升序的链表
 */
public class MergeTwoLists {

  private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 类似归并排序中的合并过程
    ListNode head = new ListNode(0);
    ListNode cur = head;
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        // 使用l1当前的头结点放入head后面
        cur.next = l1;
        cur = cur.next;
        l1 = l1.next;
      } else {
        // 使用l2当前的当前的头结点放入head后面
        cur.next = l2;
        cur = cur.next;
        l2 = l2.next;
      }
    }
    if (l2 == null) {
      // 如果l2为null了就把l1放入cur的下一位
      cur.next = l1;
    }
    if (l1 == null) {
      // 同上
      cur.next = l2;
    }
    return head.next;
  }

  public static void main(String[] args) {
    ListNode l1 = new ListNode(1);
    l1.add(2);
    l1.add(4);

    ListNode l2 = new ListNode(1);
    l2.add(3);
    l2.add(4);

    ListNode listNode = mergeTwoLists(l1, l2);
    listNode.print();
  }
}
